package com.ycl.javacore.exam.treenode;

/**
 * User: OF1089 杨成龙
 * Date: 2019/3/26
 * Time: 5:06 PM
 * Desc: 类描述
 */
public class BinaryTree {
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void setRoot(TreeNode root) {
        this.root = root;
    }

    public void insert(String value) {
        TreeNode newNode = new TreeNode(value);
        if (root == null) {
            root = newNode;
            root.setLeftTreeNode(null);
            root.setRightTreeNode(null);
        } else {
            TreeNode currentNode = root;
            TreeNode parentNode;

            while (true) {
                parentNode = currentNode;
                if (Integer.valueOf(newNode.getValue()) > Integer.valueOf(currentNode.getValue())) {
                    currentNode = currentNode.getRightTreeNode();
                    if (currentNode == null) {
                        parentNode.setRightTreeNode(newNode);
                        return;
                    }
                } else {
                    currentNode = currentNode.getLeftTreeNode();
                    if (currentNode == null) {
                        parentNode.setLeftTreeNode(newNode);
                        return;
                    }
                }
            }
        }

    }

    /**
     * 中序遍历
     *
     * @param treeNode
     */
    public void inOrder(TreeNode treeNode) {
        if (treeNode != null) {
            inOrder(treeNode.getLeftTreeNode());
            System.out.print(" " + treeNode.getValue() + " ");
            inOrder(treeNode.getRightTreeNode());
        }
    }

    /**
     * 后序遍历
     *
     * @param treeNode
     */
    public void afterOrder(TreeNode treeNode) {
        if (treeNode != null) {
            afterOrder(treeNode.getLeftTreeNode());
            afterOrder(treeNode.getRightTreeNode());
            System.out.print(" " + treeNode.getValue() + " ");
        }
    }

    /**
     * 先序遍历
     *
     * @param treeNode
     */
    public void beforeOrder(TreeNode treeNode) {
        if (treeNode != null) {
            System.out.print(" " + treeNode.getValue() + " ");
            beforeOrder(treeNode.getLeftTreeNode());
            beforeOrder(treeNode.getRightTreeNode());
        }
    }

    public TreeNode search(String key) {
        /*TreeNode currentNode = current;
        TreeNode resultNode = null;
        if (Integer.valueOf(currentNode.getValue()) == Integer.valueOf(key)) {
            resultNode = currentNode;
        } else if (Integer.valueOf(currentNode.getValue()) < Integer.valueOf(key)) {
            currentNode = currentNode.getRightTreeNode();
            search(key,currentNode);
        } else if (Integer.valueOf(currentNode.getValue()) > Integer.valueOf(key)) {
            currentNode = currentNode.getLeftTreeNode();
            search(key,currentNode);
        }

        return resultNode;*/

        TreeNode currentNode = root;
        while (currentNode != null && Integer.valueOf(currentNode.getValue()) != Integer.valueOf(key)) {
            if (Integer.valueOf(currentNode.getValue()) < Integer.valueOf(key)) {
                currentNode = currentNode.getRightTreeNode();
            } else if (Integer.valueOf(currentNode.getValue()) > Integer.valueOf(key)) {
                currentNode = currentNode.getLeftTreeNode();
            }
        }
        return currentNode;
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.insert("5");
        tree.insert("7");
        tree.insert("4");
        tree.insert("8");
        tree.insert("6");
        tree.insert("2");
        tree.insert("3");
        tree.insert("9");

        TreeNode searchNode = tree.search("6");
        System.out.println(searchNode.getValue());

        System.out.println(tree.root);
        tree.beforeOrder(tree.getRoot());
        System.out.println();
        tree.inOrder(tree.getRoot());
        System.out.println();
        tree.afterOrder(tree.getRoot());

    }

}
